//
// Created by Administrator on 2021/6/11.
//

#ifndef COMPILER_SYNTAXANALYZER_H
#define COMPILER_SYNTAXANALYZER_H

struct synTreeNode{

    int id;
    string name;
    vector<int> childId;
    synTreeNode(int Id, string Name){
        id = Id;
        name = Name;
        childId.clear();
    }
};

struct address{
    int l,a;
    address(int L, int A){
        l = L;
        a = A;
    }
};

struct instruction{
    string f;
    int l,a;
    instruction(string F, int L, int A){
        f = F;
        l = L;
        a = A;
    }
};

struct tableLine{
    string name,kind;
    int lev,val,adr;
    tableLine(){
        name = kind = "";
        lev = val = adr = 0;
    }
    tableLine(string Name ,string Kind, int Lev,int Val,int Adr){
        name = Name;
        kind = Kind;
        lev = Lev;
        val = Val;
        adr = Adr;
    }
};
struct table{
    vector<tableLine> line;
    int tableIndex,lineIndex,size;
    table(){
        tableIndex = lineIndex = -1;
        size = 3;
    }
    table(int T,int L){
        tableIndex = T;
        lineIndex = L;
        size = 3;
    }
};


struct synTree{
public:
    synTree(vector<string>& Sym, vector<string>& Label){
        sym=Sym;
        label=Label;
        indexPointer = 0;
        nestcnt = 0;
        out.clear();
        LEV = TX = 0;
        nowAdr = 3;
        ALLTABLE.push_back(table());
    }

    int addNode(string word){
        synTreeNode trNode(curNode,word);
        root.push_back(trNode);
        return curNode++;
    }
    int addNode(int fa, string word){
        synTreeNode trNode(curNode,word);
        root.push_back(trNode);
        root[fa].childId.push_back(curNode);
        return  curNode++;
    }
    int addNode(int fa){
        synTreeNode trNode(curNode,label[indexPointer++]);
        root.push_back(trNode);
        root[fa].childId.push_back(curNode);
        return  curNode++;
    }

    bool Program();
    bool SubProgram(int lastId, bool Main, int TableIndex, int LineIndex);
    bool ConstantDeclare(int lastId);
    bool ConstantDefine(int lastId);
    bool VariableDeclare(int lastId);
    bool ProcedureDeclare(int lastId);
    bool ProcedureHead(int lastId,int &tableIndex,int &lineIndex);
    bool Sentence(int lastId);
    bool Assignment(int lastId);
    bool Combined(int lastId);
    bool Condition(int lastId);
    bool Expression(int lastId);
    bool Item(int lastId);
    bool Factor(int lastId);
    bool RelationOp(int lastId);
    bool IfSentence(int lastId);
    bool CallSentence(int lastId);
    bool WhileSentence(int lastId);
    bool ReadSentence(int lastId);
    bool WriteSentence(int lastId);
    bool EmptySentence(int lastId);

    bool exsitName(string name, int idx){
        for (int i=0; i<ALLTABLE[idx].line.size(); i++){
            if (ALLTABLE[idx].line[i].name == name){
                return true;
            }
        }
        return false;
    }

    address findAd(string Name, bool proce){
        int idx = TX,lev = 0;
        while (idx != -1){
            if (proce){
                for (int i = 0; i< ALLTABLE[idx].line.size();i++){
                    if (ALLTABLE[idx].line[i].name == Name && ALLTABLE[idx].line[i].kind == "PROCEDURE"){
                        address ad(lev, ALLTABLE[idx].line[i].adr);
                        return ad;
                    }
                }
            }else {
                for (int i = 0; i< ALLTABLE[idx].line.size();i++){
                    if (ALLTABLE[idx].line[i].name == Name && ALLTABLE[idx].line[i].kind != "PROCEDURE"){
                        if (ALLTABLE[idx].line[i].kind == "VARIABLE"){
                            address ad(lev, ALLTABLE[idx].line[i].adr);
                            return ad;
                        }else {
                            address ad(-1, ALLTABLE[idx].line[i].val);
                            return ad;
                        }
                    }
                }
            }
            idx = ALLTABLE[idx].tableIndex;
            lev++;
        }
        address ad(-1, -1);
        return ad;
    }

    void dfs(int id){
        if (root[id].name == "("){
            out += "LP";
        }else if (root[id].name == ")"){
            out += "RP";
        }else if (root[id].name == ","){
            out += "COMMA";
        }else out += root[id].name;
        if (root[id].childId.size() == 0){
            return;
        }
        out += "(";
        for (int i = 0; i < root[id].childId.size();i++){
            dfs(root[id].childId[i]);
            if (i != (root[id].childId.size() - 1 )) {
                out += ",";
            }
        }
        out += ")";
        return;
    }
    void print(){
        cout<< out;
    }
    void pushInstruction(string ff, int ll, int aa){
        instructionSet.push_back(instruction(ff, ll, aa));
    }
    void printInstruction(){
        for (int i=0; i< instructionSet.size();i++){
            cout<< instructionSet[i].f<<" "<<instructionSet[i].l<<" "<<instructionSet[i].a<<endl;
        }
    }

private:
    vector<string> sym,label;
    vector<synTreeNode> root;
    vector<instruction> instructionSet;
    int indexPointer,curNode{};
    int nestcnt;
    string out;

    vector<table> ALLTABLE;
    int LEV,TX,nowAdr;

};

bool synTree::Program() {
    int fa = addNode("PROGRAM");

    if (indexPointer >= label.size()){
        //超过最后一个词 越界
        return false;
    }

    pushInstruction("JMP", 0, 0);

    if (!SubProgram(fa, true, 0, 0)){
        return false;
    }

    if (indexPointer == label.size()-1 && label[indexPointer] == "."){
        addNode(fa, ".");
        return true;
    }else {
        return false;
    }
}

bool synTree::SubProgram(int lastId, bool Main, int TableIndex, int LineIndex) {
    int fa = addNode(lastId, "SUBPROG");
    if (indexPointer > label.size()){
        //超过最后一个词 越界
        return false;
    }


    if (label[indexPointer] == "CONST"){
        if(!ConstantDeclare(fa)){
            return false;
        }
    }
    if (label[indexPointer] == "VAR"){
        if (!VariableDeclare(fa)){
            return false;
        }
    }
    if (label[indexPointer] == "PROCEDURE"){
        ++nestcnt;
        if (!ProcedureDeclare(fa)){
            return false;
        }
    }
    pushInstruction("INT",0,3);
    int Idx = instructionSet.size() - 1;
    if (Main){
        Main = false;
        instructionSet[0].a = Idx;
    }else {
        ALLTABLE[TableIndex].line[LineIndex].adr = Idx;
    }

    if(!Sentence(fa)){
        return false;
    }

    instructionSet[Idx].a = ALLTABLE[TX].size;
    pushInstruction("OPR",0,0);//return 0
    return true;
}

bool synTree::ConstantDeclare(int lastId) {
    int fa = addNode(lastId, "CONSTANTDECLARE");
    if (indexPointer > label.size() || label[indexPointer] != "CONST"){
        //超过最后一个词 越界
        return false;
    }
    addNode(fa);
    if (!ConstantDefine(fa)){
        return false;
    }
    while (label[indexPointer] == ","){
        addNode(fa);
        if (!ConstantDefine(fa)){
            return false;
        }
    }

    if (label[indexPointer] != ";"){
        return false;
    }
    addNode(fa);
    return true;
}

bool synTree::ConstantDefine(int lastId)  {
    int fa = addNode(lastId, "CONSTANTDEFINE");
    if (indexPointer > label.size() || sym[indexPointer] != "Identifier"){
        //超过最后一个词 越界
        return false;
    }
    tableLine tl(label[indexPointer], "CONSTANT", 0, 0, 0);

    addNode(fa);
    if (label[indexPointer] != "="){
        return false;
    }
    addNode(fa);
    if (sym[indexPointer] != "Number"){
        return false;
    }
    tl.val = atoi(label[indexPointer].c_str());
    addNode(fa);
    if (!exsitName(tl.name, TX)){
        ALLTABLE[TX].line.push_back(tl);
    }else {
        return false;
    }
    return true;
}

bool synTree::VariableDeclare(int lastId) {
    int fa = addNode(lastId, "VARIABLEDECLARE");
    if (indexPointer > label.size() || label[indexPointer] != "VAR"){
        //超过最后一个词 越界
        return false;
    }
    addNode(fa);
    if (sym[indexPointer] != "Identifier"){
        return false;
    }
    tableLine tl(label[indexPointer],"VARIABLE",LEV,0,nowAdr++);
    if (!exsitName(tl.name, TX)){
        ALLTABLE[TX].line.push_back(tl);
        ALLTABLE[TX].size += 1;
    }else {
        return false;
    }
    addNode(fa);
    while (label[indexPointer] == ","){
        addNode(fa);
        if (sym[indexPointer] != "Identifier"){
            return false;
        }
        tableLine tl(label[indexPointer],"VARIABLE",LEV,0,nowAdr++);
        if (!exsitName(tl.name, TX)){
            ALLTABLE[TX].line.push_back(tl);
            ALLTABLE[TX].size += 1;
        }else {
            return false;
        }
        addNode(fa);
    }
    if (label[indexPointer] != ";"){
        return false;
    }
    addNode(fa);
    return true;
}

bool synTree::ProcedureDeclare(int lastId) {
    LEV += 1;
    if (LEV > 3){
        return false;
    }
    int fa = addNode(lastId, "PROCEDUREDECLARE");
    if (indexPointer > label.size()){
        //超过最后一个词 越界
        return false;
    }
    int tableIndex,lineIndex;

    if (!ProcedureHead(fa,tableIndex,lineIndex)){
        return false;
    }
    if (!SubProgram(fa,false,tableIndex,lineIndex)){
        return false;
    }
    if (label[indexPointer] != ";"){
        return false;
    }
    addNode(fa);
    LEV -= 1;
    int ti = ALLTABLE[TX].tableIndex;
    int li = ALLTABLE[TX].lineIndex;
    TX = ti;
    nowAdr = ALLTABLE[TX].line[li].adr + 1;
    while (label[indexPointer] == "PROCEDURE"){
        if (!ProcedureDeclare(fa)){
            return false;
        }
    }
    return true;
}

bool synTree::ProcedureHead(int lastId,int &tableIndex,int &lineIndex) {
    int fa = addNode(lastId,"PROCEDUREHEAD");
    if (indexPointer > label.size() || label[indexPointer] != "PROCEDURE"){
        //超过最后一个词 越界
        return false;
    }
    addNode(fa);
    if (sym[indexPointer] != "Identifier"){
        return false;
    }
    ALLTABLE.push_back(table());
    int nowTX = ALLTABLE.size() - 1;
    tableLine tl(label[indexPointer], "PROCEDURE", LEV-1, 0 ,instructionSet.size());
    if (!exsitName(tl.name,TX)){
        ALLTABLE[TX].line.push_back(tl);
        tableIndex = TX;
        lineIndex = ALLTABLE[TX].line.size() - 1;
        ALLTABLE[nowTX].tableIndex = TX;
        ALLTABLE[nowTX].lineIndex = ALLTABLE[TX].line.size()-1;
        TX = nowTX;
        nowAdr = 3;//DX
    }else {
        return false;
    }
    addNode(fa);
    if (label[indexPointer] != ";"){
        return false;
    }
    addNode(fa);
    return true;
}

bool synTree::Sentence(int lastId) {
    int fa = addNode(lastId,"SENTENCE");
    if (indexPointer > label.size()){
        //超过最后一个词 越界
        return false;
    }
    if (sym[indexPointer] != "Identifier" && label[indexPointer] != "IF" && label[indexPointer] != "WHILE"
        && label[indexPointer] != "CALL" && label[indexPointer] != "READ" && label[indexPointer] != "WRITE"
        && label[indexPointer] != "BEGIN"){
        EmptySentence(fa);
    }
    if (sym[indexPointer] == "Identifier" && !Assignment(fa)){
        return false;
    }
    if (label[indexPointer] == "IF" && !IfSentence(fa)){
        return false;
    }
    if (label[indexPointer] == "WHILE" && !WhileSentence(fa)){
        return false;
    }
    if (label[indexPointer] == "CALL" && !CallSentence(fa)){
        return false;
    }
    if (label[indexPointer] == "READ" && !ReadSentence(fa)){
        return false;
    }
    if (label[indexPointer] == "WRITE" && !WriteSentence(fa)){
        return false;
    }
    if (label[indexPointer] == "BEGIN" && !Combined(fa)){
        return false;
    }
    return true;
}

bool synTree::Assignment(int lastId) {
    int fa = addNode(lastId, "ASSIGNMENT");
    if (indexPointer > label.size()){
        //超过最后一个词 越界
        return false;
    }
    if (sym[indexPointer] != "Identifier"){
        return false;
    }
    addNode(fa);
    if (label[indexPointer] != ":="){
        return false;
    }
    addNode(fa);
    address ad = findAd(label[indexPointer - 2], false);

    if (ad.l == -1){
        return false;
    }
    if (!Expression(fa)){
        return false;
    }
    pushInstruction("STO", ad.l,ad.a);
    return true;
}

bool synTree::Combined(int lastId) {
    int fa = addNode(lastId, "COMBINED");
    if (indexPointer > label.size()){
        //超过最后一个词 越界
        return false;
    }
    if (label[indexPointer] != "BEGIN"){
        return false;
    }
    addNode(fa);
    if (!Sentence(fa)){
        return false;
    }
    while (label[indexPointer] == ";"){
        addNode(fa);
        if (!Sentence(fa)){
            return false;
        }
    }
    if (label[indexPointer] != "END"){
        return false;
    }
    addNode(fa);
    return true;
}

bool synTree::Condition(int lastId) {
    int fa = addNode(lastId, "CONDITION");
    if (indexPointer > label.size()){
        //超过最后一个词 越界
        return false;
    }
    if (label[indexPointer] == "ODD"){
        addNode(fa);
        if (!Expression(fa)){
            return false;
        }
        pushInstruction("OPR", 0, 1);
    }else {
        if (!Expression(fa)){
            return false;
        }
        string nowOP = label[indexPointer];
        if (!RelationOp(fa)){
            return false;
        }
        if (!Expression(fa)){
            return false;
        }
        if (nowOP == "=") pushInstruction("OPR", 0, 2);
        else if (nowOP == "#") pushInstruction("OPR", 0 ,3);
        else if (nowOP == "<") pushInstruction("OPR", 0 ,4);
        else if (nowOP == "<=") pushInstruction("OPR", 0 ,5);
        else if (nowOP == ">") pushInstruction("OPR", 0 ,6);
        else if (nowOP == ">=") pushInstruction("OPR", 0 ,7);
    }
    return true;
}

bool synTree::Expression(int lastId) {
    int fa = addNode(lastId, "EXPRESSION");
    if (indexPointer > label.size()){
        //超过最后一个词 越界
        return false;
    }
    bool negative = false;
    if (label[indexPointer] == "+" || label[indexPointer] == "-"){
        if (label[indexPointer] == "-") negative = true;
        addNode(fa);
    }
    if (!Item(fa)){
        return false;
    }
    if (negative) {
        pushInstruction("OPR", 0, 8);
    }
    while (label[indexPointer] == "+" || label[indexPointer] == "-"){
        bool plus;
        if (label[indexPointer] == "+") plus = true;else plus = false;
        addNode(fa);
        if (!Item(fa)){
            return false;
        }
        if (plus) pushInstruction("OPR", 0, 9);
        else pushInstruction("OPR", 0, 10);
    }
    return true;
}

bool synTree::Item(int lastId) {
    int fa = addNode(lastId, "ITEM");
    if (indexPointer > label.size()){
        //超过最后一个词 越界
        return false;
    }
    if (!Factor(fa)){
        return false;
    }
    while (label[indexPointer] == "*" || label[indexPointer] == "/"){
        bool mul;
        if (label[indexPointer] == "*") mul = true;else mul = false;
        addNode(fa);
        if (!Factor(fa)){
            return false;
        }
        if (mul) pushInstruction("OPR", 0, 11);
        else pushInstruction("OPR", 0, 12);
    }
    return true;
}

bool synTree::Factor(int lastId) {
    int fa = addNode(lastId, "FACTOR");
    if (indexPointer > label.size()){
        //超过最后一个词 越界
        return false;
    }
    if (label[indexPointer] == "("){
        addNode(fa);
        if (!Expression(fa)){
            return false;
        }
        if (label[indexPointer] != ")"){
            return false;
        }else {
            addNode(fa);
            return true;
        }
    }
    if (sym[indexPointer] == "Identifier"){
        address ad = findAd(label[indexPointer], false);
        if (ad.l == -1 && ad.a == -1){
            return false;
        }
        if (ad.l == -1){
            pushInstruction("LIT", 0, ad.a);
        }else{
            pushInstruction("LOD", ad.l, ad.a);
        }
        addNode(fa);
        return true;
    }
    if (sym[indexPointer] == "Number"){
        pushInstruction("LIT", 0, atoi(label[indexPointer].c_str()));
        addNode(fa);
        return true;
    }
    return false;
}

bool synTree::RelationOp(int lastId) {
//    int fa = addNode(lastId, word);
    if (indexPointer > label.size()){
        //超过最后一个词 越界
        return false;
    }
    if (label[indexPointer] == "=" || label[indexPointer] == "#" || label[indexPointer] == "<"
        || label[indexPointer] == "<=" || label[indexPointer] == ">" || label[indexPointer] == ">="){
        addNode(lastId);
        return true;
    }else{
        return false;
    }
}

bool synTree::IfSentence(int lastId) {
    int fa = addNode(lastId, "IFSENTENCE");
    if (indexPointer > label.size()){
        //超过最后一个词 越界
        return false;
    }
    if (label[indexPointer] != "IF"){
        return false;
    }
    addNode(fa);
    if (!Condition(fa)){
        return false;
    }
    pushInstruction("JPC", 0, 0);
    int idx = instructionSet.size()-1;
    if (label[indexPointer] != "THEN"){
        return false;
    }
    addNode(fa);
    if (!Sentence(fa)){
        return false;
    }
    instructionSet[idx].a = instructionSet.size();
    return true;
}

bool synTree::CallSentence(int lastId) {
    int fa = addNode(lastId, "CALLSENTENCE");
    if (indexPointer > label.size()){
        //超过最后一个词 越界
        return false;
    }
    if (label[indexPointer] != "CALL"){
        return false;
    }
    addNode(fa);
    if (sym[indexPointer] != "Identifier"){
        return false;
    }
    address ad = findAd(label[indexPointer], true);
    if (ad.l == -1 && ad.a==-1){
        return false;
    }
    pushInstruction("CAL",ad.l,ad.a);
    addNode(fa);
    return true;
}

bool synTree::WhileSentence(int lastId) {
    int fa = addNode(lastId, "WHILESENTENCE");
    if (indexPointer > label.size()){
        //超过最后一个词 越界
        return false;
    }
    if (label[indexPointer] != "WHILE"){
        return false;
    }
    addNode(fa);
    int loop = instructionSet.size();
    if (!Condition(fa)){
        return false;
    }
    int jump = instructionSet.size();
    pushInstruction("JPC", 0, 0);
    if (label[indexPointer] != "DO"){
        return false;
    }
    addNode(fa);
    if (!Sentence(fa)){
        return false;
    }
    pushInstruction("JMP",0,loop);
    instructionSet[jump].a = instructionSet.size();
    return true;
}

bool synTree::ReadSentence(int lastId) {
    int fa = addNode(lastId, "READSENTENCE");
    if (indexPointer > label.size()){
        //超过最后一个词 越界
        return false;
    }
    if (label[indexPointer] != "READ"){
        return false;
    }
    addNode(fa);
    if (label[indexPointer] != "("){
        return false;
    }
    addNode(fa);
    if (sym[indexPointer] != "Identifier"){
        return false;
    }
    pushInstruction("OPR",0 , 13);
    address ad = findAd(label[indexPointer],false);
    if (ad.a == -1 && ad.l==-1){
        return false;
    }
    if (ad.l == -1){
        return false;
    }
    pushInstruction("STO", ad.l, ad.a);
    addNode(fa);
    while (label[indexPointer] == ","){
        addNode(fa);
        if (sym[indexPointer] != "Identifier"){
            return false;
        }
        pushInstruction("OPR",0 , 13);
        address ad = findAd(label[indexPointer],false);
        if (ad.a == -1 && ad.l==-1){
            return false;
        }
        if (ad.l == -1){
            return false;
        }
        pushInstruction("STO", ad.l, ad.a);
        addNode(fa);
    }
    if (label[indexPointer] != ")"){
        return false;
    }
    addNode(fa);
    return true;
}

bool synTree::WriteSentence(int lastId) {
    int fa = addNode(lastId, "WRITESENTENCE");
    if (indexPointer > label.size()){
        //超过最后一个词 越界
        return false;
    }
    if (label[indexPointer] != "WRITE"){
        return false;
    }
    addNode(fa);
    if (label[indexPointer] != "("){
        return false;
    }
    addNode(fa);
    if (sym[indexPointer] != "Identifier"){
        return false;
    }
    address ad = findAd(label[indexPointer],false);
    if (ad.a == -1 && ad.l==-1){
        return false;
    }
    if (ad.l == -1){
        pushInstruction("LIT", 0, ad.a);
    }else {
        pushInstruction("LOD", ad.l, ad.a);
    }
    pushInstruction("OPR", 0 , 14);
    addNode(fa);
    while (label[indexPointer] == ","){
        addNode(fa);
        if (sym[indexPointer] != "Identifier"){
            return false;
        }
        address ad = findAd(label[indexPointer],false);
        if (ad.a == -1 && ad.l==-1){
            return false;
        }
        if (ad.l == -1){
            pushInstruction("LIT", 0, ad.a);
        }else {
            pushInstruction("LOD", ad.l, ad.a);
        }
        pushInstruction("OPR", 0 , 14);
        addNode(fa);
    }
    if (label[indexPointer] != ")"){
        return false;
    }
    addNode(fa);
    return true;
}

bool synTree::EmptySentence(int lastId) {
    addNode(lastId, "EMPTY");
    return false;
}


bool SyntaxAnalyzer(vector<string>& sym, vector<string>& label){
    synTree tr(sym,label);
    if (tr.Program()) {
//        tr.dfs(0);
//        tr.print();
        tr.printInstruction();
        return true;
    }else return false;
}

#endif //COMPILER_SYNTAXANALYZER_H
